#include<iostream>
#include<stack>
using namespace std;

template<class T>
class BinaryTreeNode{
	friend class BinaryTree<T>;
public:
    T element;
    BinaryTreeNode<T> * rightChild;
    BinaryTreeNode<T> * leftChild;

    BinaryTreeNode();
    BinaryTreeNode(const t & ele);
    BinaryTreeNode(const t &ele, BinaryTreeNode<T> *l, BinaryTreeNode<T> *r);
    BinaryTreeNode<T> *getLeftChild() const;
    BinaryTreeNode<T> *getRightChild() const;
    void setLeftChild(BinaryTreeNode<T> * l);
    void setTightChild(BinaryTreeNode<T> *r);
    T getValue() const;
    void setValue(const T & val);
    vool isLeaf() const;
};


template<class T>
class BinaryTree{
private:
    BinaryTreeNode<T> *root;
public:
    BinaryTree();
    ~BinaryTree();
    bool isEmpty() const;
    BinaryTreeNode<T> * getRoot() const;
    BinaryTreeNode<T> * getParent(BinaryTreeNode<T>*current) const;
    BinaryTreeNode<T> * getLeftSibling(BinaryTreeNode<T>*current)const;
    BinaryTreeNode<T> * getRightSibling(BinaryTreeNode<T> * current)const;
    void breadthFirstOrder(BinaryTreeNode<T> * root);
    void inOrder(BinaryTreeNode<T> * root);
    void preOrder(BinaryTreeNode<T> * root);
    void postOrder(BinaryTreeNode<T> * root);
    void levelOrder(BinaryTreeNode<T> * root);
    void deleteBinaryTree(BinaryTreeNode<T> * root);
    void preOrderWithoutRecusion(BinaryTreeNode<T> * root);
    void inOrderWithourRecusion(BinaryTreeNode<T> *root);
    void postOrderWithoutRecursion(BinaryTreeNode<T>*root);
};


template<class T>
BinaryTree::~BinaryTree(){
    deleteBinaryTree(root);
}

template<class T>
void BinaryTree<T>::levelOrder(BinaryTreeNode<T> *root){
    using std::queue;
    queue<BinaryTreeNode <T> *>  nodeQueue;
    BinaryTreeNode<T> *pointer = root;

    if(pointer)
        nodeQueue.push(pointer);
    while(!nodeQueue.empty()){
        pointer = nodeQueue.front();
        cout<<pointer->element<<"\t";
    }
}


template<class T>
void BinaryTree<T>::preOrder(BinaryTreeNode<T> *root){
    if(root!=NULL){
        cout<<root->element<<"\t";
        preOrder(root->leftChild);
        preOrder(root->rightChild);
    }
}


template<class T>
void BinaryTree<T>::inOrder(BinaryTreeNode<T> *root){
    if(root!=NULL){
        inOrder(root->leftChild);
        cout<<root->element<<"\t";
        inOrder(root->rightChild);
    }
}

template<class T>
void BinaryTree<T>::postOrder(BinaryTreeNode<T> *root){
    if(root!=NULL){
        postOrder(root->leftChild);
        postOrder(root->rightChild);
    }
}

template<class T>
void BinaryTree<T>::preOrderWithoutRecusion(BinaryTreeNode<T> *root){
    using std::stack;
    stack<BinaryTreeNode<T>*>nodestack;
    BinaryTreeNode<T>* pointer=root;

    while(!nodestack.empty()||pointer){
        if(pointer){
            cout<<pointer->element<<"\t";
            if(pointer->rightChild)
                nodestack.push(pointer->rightChild);
            pointer=pointer->leftChild;
        }
        else{
            pointer=nodestack.top();
            nodestack.pop();
        }
    }

//    using std::stack;
//    stack<BinaryTreeNode<T>*>nodestack;

//    BinaryTreeNode<T> *pointer= root;

//    while(!nodestack.empty()||pointer){
//        if(pointer){
//            visit(poiner);
//            if(pointer->rightChild!=NULL)
//                nodestack.push(pointer->rightChild);
//            pointer=pointer->leftChild;
//        }
//        else{
//            pointer = nodestack.top();
//            nodestack.pop();
//        }
//    }
}


template<class T>
void BinaryTree<T>::inOrderWithourRecusion(BinaryTreeNode<T> *root){
    using std::stack;
    stack<BinaryTreeNode<T>*> nodestack;
    BinaryTreeNode<T>* pointer=root;

    while(!nodestack.empty()||pointer){
        if(pointer==NULL){
            pointer=nodestack.top();
            cout<<pointer->element<<"\t";
            nodestack.pop();

            pointer=pointer->rightChild;
        }
        else{
            nodestack.push(pointer);
            pointer=pointer->leftChild;
        }
    }

//    using::stack;
//    stack<BinaryTreeNode<T>*>nodestack;
//    BinaryTreeNode<T>* pointer =root;

//    while(!nodestack.empty()||pointer){
//        if(pointer)
//        {
//            nodestack.push(pointer);
//            pointer=pointer->leftChild;
//        }
//        else{
//            pointer=nodestack.top();
//            cout<<pointer->element<<"\t";
//            pointer=pointer->rightChild;
//            nodestack.pop();
//        }
//    }
}


template<class T>
void BinaryTree<T>::postOrderWithoutRecursion(BinaryTreeNode<T> *root){
    using std::stack;
    stack<BinaryTreeNode<T>*>nodestack;
    BinaryTreeNode<T>*pointer=root;
    BinaryTreeNode<T>*pre=root;

    while(pointer){
        for(;pointer->leftChild!=NULL;pointer=pointer->leftChild)
            nodestack.push(pointer);
        while(pointer!=NULL&&(pointer->rightChild==NULL&&pointer->rightChild==pre)){
            cout<<pointer->element<<"\t";
            pre=pointer;
            if(nodestack.empty())
                break;
            pointer=nodestack.top();
            nodestack.pop();
        }
        nodestack.push(pointer);
        pointer=pointer->rightChild;
    }
//    using std::stack;
//    stack<BinaryTreeNode<T>*> nodestack;
//    BinaryTreeNode<T>* pointer=root;
//    BinaryTreeNode<T>* pre=root;

//    while(pointer){
//        for(;pointer->leftChild!=NULL;pointer=pointer->leftChild)
//            nodestack.push(pointer);
//        while(pointer!=NULL&&(pointer->rightChild==NULL||pointer->rightChild==pre)){
//            cout<<pointer->element<<"\t";
//            pre=pointer;

//            if(nodestack.empty())
//                break;
//            pointer=nodestack.top();
//            nodestack.pop();
//        }

//        nodestack.push(pointer);
//        pointer=pointer->rightChild;
//    }
}
